1334E - Divisor Paths - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long kq,ts[65],i,sl,nto[101],s,t,x,q,gt[102],ng[102];
long long lt(long long a,long long b)
{
    if(b==0) return 1;
    long long tg=lt(a,b/2);
    if(b%2==0) return tg*tg%mod;
    return tg*tg%mod*a%mod;
}
int main()
{
 //   freopen("ntu.inp","r",stdin);
 //   freopen("ntu.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>x;
    for(i=2;i*i<=x;i++)
        if(x%i==0)
        {
            nto[++sl]=i;
            while(x%i==0) x/=i;
        }
    if(x>1) nto[++sl]=x;
    cin>>q;
    gt[0]=1;
    for(i=1;i<=101;i++) gt[i]=gt[i-1]*i%mod;
    ng[101]=lt(gt[101],mod-2);
    for(i=100;i>=0;i--) ng[i]=ng[i+1]*(i+1)%mod;
    while(q--)
    {
        cin>>s>>t;
        kq=1;
        x=__gcd(s,t);
        s/=x; t/=x;
        memset(ts,0,sizeof(ts));
        int dem=0;
        for(i=1;i<=sl;i++)
        {
            int cnt=0;
            while(s%nto[i]==0) { cnt++; s/=nto[i]; }
            dem+=cnt;
            kq=kq*ng[cnt]%mod;
        }
        kq=kq*gt[dem]%mod;
        dem=0;
        for(i=1;i<=sl;i++)
        {
            int cnt=0;
            while(t%nto[i]==0) { cnt++; t/=nto[i]; }
            dem+=cnt;
            kq=kq*ng[cnt]%mod;
        }
        kq=kq*gt[dem]%mod;
        cout<<kq<<'\n';
    }
}